This relates generally to rendering primitives during graphics processing.
An image to be processed may be analyzed in terms of primitives, such as triangles or polygons, which collectively represent the overall graphics image. In many cases, the triangles or polygons are analyzed during rasterization.
Commonly graphics primitives are searched. One common task in graphics processing is to determine which polygons or triangles are located in a given tile or frustrum. This may involve a geometrical proximity search among suitable primitives. Another example of the need for searching primitives is in ray tracing. There a closest polygon that is intersected by a ray or group of rays is identified through a search algorithm.
Rendering algorithms use acceleration structures to reduce the complexity of solving search problems. These acceleration structures may also be known as spatial or geometrical indices. Typically, they involve a hierarchical tree-like data structure storing primitives at terminal nodes. Examples of such hierarchical acceleration structures include the k dimensional tree or kd-tree, bounding volume hierarchy (BVH), bounding interval hierarchy (BIH), or binary space partition (BSP).